UVa/10000 - Longest Paths/10000.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <queue>
   5 #include <iostream>
   6 #include <vector>
   7
   8 using namespace std;
   9
  10 int main(){
  11   int n;
  12   int C = 1;
  13   while (cin >> n && n){
  14     int start;
  15     cin >> start, --start;
  16
  17     vector<int> g[n];
  18     int p, q;
  19     while (cin >> p >> q && (p+q)){
  20       --p, --q;
  21       g[p].push_back(q);
  22     }
  23     for (int i=0; i<n; ++i){
  24       sort(g[i].begin(), g[i].end());
  25     }
  26
  27     int answer = -1, length = -1;
  28     priority_queue<pair<int, int> > Q; //First = distance, second = destiny
  29     int visited[n];
  30     for (int i=0; i<n; ++i) visited[i] = -1;
  31     Q.push(make_pair(0, -start));
  32     while (Q.size()){
  33       int u = -Q.top().second;
  34       int w = Q.top().first;
  35       //cout << "Saque " << u + 1 << " " << w << endl;
  36       Q.pop();
  37
  38       if (visited[u] > w) continue;
  39
  40       if (w > length || (w == length && u < answer)){ //En esta línea estaba el bug...
  41         answer = u;
  42         length = w;
  43       }
  44       vector<int> &vecinos = g[u];
  45       for (int i=0; i<vecinos.size(); ++i){
  46         if (visited[vecinos[i]] < w + 1){
  47           visited[vecinos[i]] = w + 1;
  48           Q.push(make_pair(w + 1, -vecinos[i]));
  49         }
  50       }
  51     }
  52     cout << "Case " << C++ << ": The longest path from " << start + 1 << " has length ";
  53     cout  << length << ", finishing at " << answer + 1 << "." << endl << endl;
  54   }
  55   return 0;
  56 }